﻿#pragma once
#include "../PreInclude.h"

namespace ThreeSumCloset
{
    /**
     * 最接近的三数之和
     * https://leetcode.cn/problems/3sum-closest/description/
     *
     * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。返回这三个数的和。
     * 假定每组输入只存在恰好一个解。
     */
    class IQustion
    {
    public:
        virtual int threeSumClosest(std::vector<int>& nums, int target) =0;
    };

    class Solution:public IQustion
    {
    public:
        int threeSumClosest(vector<int>& nums, int target) override
        {
            std::sort(nums.begin(), nums.end());
            const int n = nums.size();
            int diff = INT_MAX;

            for (int i = 0; i <= n - 3; ++i)
            {
                if (i > 0 && nums[i] == nums[i - 1])
                    continue;
                const int want = target-nums[i];
                if (nums[i + 1] + nums[i + 2] > want)
                {
                    updateDiff(diff, nums[i] + nums[i + 1] + nums[i + 2], target);
                    continue;
                }
                if (nums[n - 2] + nums[n - 1] < want)
                {
                    updateDiff(diff, nums[i] + nums[n - 2] + nums[n - 1], target);
                    continue;
                }

                int left = i + 1, right = n - 1;
                while (left < right)
                {
                    updateDiff(diff, nums[i] + nums[left] + nums[right], target);
                    if(diff == 0)
                        return target;
                    if(left < right && nums[left] + nums[right] < want)
                        left++;
                    else
                        right--;
                }
            }

            return target + diff;
        }
    private:
        void updateDiff(int& diff, int sum, int target)
        {
            int curDiff = sum - target;
            if (std::abs(curDiff) < std::abs(diff))
                diff = curDiff;
        }
    };

    struct TestParams
    {
        string numsStr;
        int target;
        int expectAns;

        int InputParams(IQustion* ques) const
        {
            vector<int> nums= TestingUtil::parseNums<int>(numsStr);
            return ques->threeSumClosest(nums,target);
        }
    };
    class ThreeSumClosetTestSuite:public testing::TestWithParam<TestParams>
    {
    };
    TEST_P(ThreeSumClosetTestSuite,case1)
    {
        TEST_SOLUTION1(IQustion,Solution,&)
        {
            TestParams params= GetParam();
            int ans=  params.InputParams(solution);
            EXPECT_EQ(ans,params.expectAns);
        };
    }
    INSTANTIATE_TEST_SUITE_P(TestThreeSumClosetTest,
           ThreeSumClosetTestSuite,
           testing::Values(
               TestParams{"[4,0,5,-5,3,3,0,-4,-5]",-2,-2},
               TestParams{"[2,3,8,9,10]",16,15},
               TestParams{"[-1000,-5,-5,-5,-5,-5,-5,-1,-1,-1]",-8,-7},
               TestParams{"[-4,2,2,3,3,3]",0,0}
               ));

}
